package no10;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/25 11:28
 * 斐波那契数列
 * https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
 */
public class Solution {

    // <k, v> 表示第 k 个斐波那契的为 v
    private Map<Integer, Integer> map = new HashMap<>();

    // 方法1. 递归效率低 -> 尝试递归 + 剪枝
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        if (n == 2) {
            return 1;
        }
        // fib(n) = fib(n-2) + fib(n-1)
        int prePre = 0; // 表示 fib(n-2)
        if (map.containsKey(n-2)) {
            prePre = map.get(n-2);
        } else {
            prePre = fib(n-2) % 1000000007;
        }
        int pre = 0; // 表示 fib(n-1)
        if (map.containsKey(n-1)) {
            pre = map.get(n-1);
        } else {
            pre = fib(n-1) % 1000000007;
        }
        return (pre + prePre) % 1000000007;
    }

    // 方法2. 迭代方式
    public int fib2(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;
    }

    // 用于测试
    public static void main(String[] args) {
        Solution solution = new Solution();
        int fib = solution.fib(45);
        int fib2 = solution.fib2(45);
        System.out.println(fib + " " + fib2);
    }
}
